{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Unique Binary String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findDifferentBinaryString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出不同的二进制字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串数组 <code>nums</code> ，该数组由 <code>n</code> 个 <strong>互不相同</strong> 的二进制字符串组成，且每个字符串长度都是 <code>n</code> 。请你找出并返回一个长度为&nbsp;<code>n</code>&nbsp;且&nbsp;<strong>没有出现</strong> 在 <code>nums</code> 中的二进制字符串<em>。</em>如果存在多种答案，只需返回 <strong>任意一个</strong> 即可。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [\"01\",\"10\"]\n",
    "<strong>输出：</strong>\"11\"\n",
    "<strong>解释：</strong>\"11\" 没有出现在 nums 中。\"00\" 也是正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [\"00\",\"01\"]\n",
    "<strong>输出：</strong>\"11\"\n",
    "<strong>解释：</strong>\"11\" 没有出现在 nums 中。\"10\" 也是正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [\"111\",\"011\",\"001\"]\n",
    "<strong>输出：</strong>\"101\"\n",
    "<strong>解释：</strong>\"101\" 没有出现在 nums 中。\"000\"、\"010\"、\"100\"、\"110\" 也是正确答案。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 16</code></li>\n",
    "\t<li><code>nums[i].length == n</code></li>\n",
    "\t<li><code>nums[i] </code>为 <code>'0'</code> 或 <code>'1'</code></li>\n",
    "\t<li><code>nums</code> 中的所有字符串 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-unique-binary-string](https://leetcode.cn/problems/find-unique-binary-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-unique-binary-string](https://leetcode.cn/problems/find-unique-binary-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[\"01\",\"10\"]', '[\"00\",\"01\"]', '[\"111\",\"011\",\"001\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        nums = set(nums)\n",
    "        n = len(nums)\n",
    "        base = [\"0\"] * n\n",
    "        for i in range(n+1):\n",
    "            if ''.join(base) not in nums:\n",
    "                return ''.join(base)         \n",
    "            base[i] = \"1\"\n",
    "\n",
    "        # def dfs(i):\n",
    "        #     if ''.join(base) not in nums:\n",
    "        #         return True\n",
    "        #     base[i] = \"1\"\n",
    "        #     if dfs(i+1):\n",
    "        #         return True\n",
    "        #     base[i] = \"0\"\n",
    "        #     if dfs(i+1):\n",
    "        #         return True\n",
    "        #     return False\n",
    "        \n",
    "        # dfs(0)\n",
    "        # return ''.join(base)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        asw=''\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i][i]=='0':\n",
    "                asw += '1'\n",
    "            else:\n",
    "                asw += '0'\n",
    "        return asw"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        vals = {int(num, 2) for num in nums}\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "        res = \"{:b}\".format(val)\n",
    "        return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        ret = '1' * len(nums[0])\n",
    "        dq = deque(nums)\n",
    "        nums = set(nums)\n",
    "        while ret in nums:\n",
    "            tmp = list(int(x) for x in ret)\n",
    "            x = dq.popleft()\n",
    "            for i in range(len(x)):\n",
    "                tmp[i] ^= int(x[i])\n",
    "                ret = ''.join(map(str, tmp))\n",
    "                if ret not in nums:\n",
    "                    break\n",
    "            dq.append(x)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        vals = set(int(x, 2) for x in nums)\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "        ret = str(bin(val))[2:]\n",
    "        return '0' * (len(nums) - len(ret)) + ret\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return ''.join(chr(ord(nums[i][i]) ^ 1) for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        # 预处理对应整数的哈希集合\n",
    "        vals = {int(num, 2) for num in nums}\n",
    "        # 寻找第一个不在哈希集合中的整数\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "        # 将整数转化为二进制字符串返回\n",
    "        res = \"{:b}\".format(val)\n",
    "        return '0' * (n - len(res)) + res\n",
    "\n",
    "#作者：力扣官方题解\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: list[str]) -> str:\n",
    "        s,s1= [],''\n",
    "        for i in nums:\n",
    "            s.append(int(i, 2))\n",
    "        for i in range(0, pow(2, len(nums[0]))):\n",
    "            if i not in s:\n",
    "                s1=str(bin(i))[2:]\n",
    "                break\n",
    "        if len(s1)==len(nums[0]):\n",
    "            return s1\n",
    "        else:\n",
    "            s2=(len(nums[0])-len(s1))*'0'\n",
    "            return s2+s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return ''.join(chr(ord(nums[i][i]) ^ 1) for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: list[str]) -> str:\n",
    "        ans = []\n",
    "        for i in range(len(nums)):\n",
    "            curr = nums[i][i]\n",
    "            ans.append(\"1\" if curr == \"0\" else \"0\")\n",
    "\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        s = set(nums)\n",
    "        for i in range(1 << n):\n",
    "            t = bin(i)[2:]\n",
    "            t = '0' * (n - len(t)) + t\n",
    "            if t not in s:\n",
    "                return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return \"\".join(str(1 - int(nums[i][i])) for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         n, st = len(nums), set()\n",
    "#         for v in nums: st.add(v)\n",
    "#         for i in range(1 << n, 1 << (n+1)):\n",
    "#             s = bin(i)[3:]\n",
    "#             if s not in st: return s\n",
    "#         return \"\"  # never!\n",
    "\n",
    "class Solution(object):\n",
    "    def findDifferentBinaryString(self, nums):\n",
    "        res = ''\n",
    "        for i in range(len(nums)):\n",
    "            res += '1' if nums[i][i] == '0' else '0'\n",
    "        return res\n",
    "\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         nums = set(nums)\n",
    "#         return next(\n",
    "#             s for p in product(\"01\", repeat=len(nums)) if (s := \"\".join(p)) not in nums\n",
    "#         )\n",
    "\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         n = len(nums)\n",
    "#         # 预处理对应整数的哈希集合\n",
    "#         vals = {int(num, 2) for num in nums}\n",
    "#         # 寻找第一个不在哈希集合中的整数\n",
    "#         val = 0\n",
    "#         while val in vals:\n",
    "#             val += 1\n",
    "#         # 将整数转化为二进制字符串返回\n",
    "#         res = \"{:b}\".format(val)\n",
    "#         return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i, j in enumerate(nums):\n",
    "            if i != int(j, 2):\n",
    "                return bin(i)[2:].zfill(n)\n",
    "        return bin(n)[2:].zfill(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        mx = 2 ** n - 1\n",
    "        while 1:\n",
    "            rd = randint(0, mx)\n",
    "            tmp = bin(rd)[2:].zfill(n)\n",
    "            if tmp not in nums:\n",
    "                return tmp "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i != int(nums[i], 2):\n",
    "                return bin(i)[2:].zfill(n)\n",
    "        return bin(n)[2:].zfill(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        s=set(nums)\n",
    "        ss=set()\n",
    "        for x in nums:\n",
    "            cur=0\n",
    "            x=list(x)\n",
    "            for y in x:\n",
    "                cur<<=1\n",
    "                cur+=int(y)\n",
    "            ss.add(cur)\n",
    "\n",
    "        n=len(nums[0])\n",
    "        for i in count(0):\n",
    "            if i not in ss:\n",
    "                ans=bin(i)[2:]\n",
    "                return \"0\"*(n-len(ans))+ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        _map = {\"1\": \"0\", \"0\": \"1\"}\n",
    "        # return \"\".join([_map[nums[i][i]] for i in range(len(nums))])\n",
    "        res = \"\"\n",
    "        for i in range(len(nums)):\n",
    "            res += _map[nums[i][i]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        ans = ''\n",
    "        for i in range(n):\n",
    "            if nums[i][i] == '1':\n",
    "                ans += '0'\n",
    "            else:\n",
    "                ans += '1'\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: list[str]) -> str:\n",
    "        return ''.join(str((int(nums[i][i])^1)%2) for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: list[str]) -> str:\n",
    "        s,s1= [],''\n",
    "        for i in nums:\n",
    "            s.append(int(i, 2)) #将二进制转为十进制\n",
    "        #找不在范围里的数\n",
    "        for i in range(0, pow(2, len(nums[0]))):\n",
    "            if i not in s:\n",
    "                s1=str(bin(i))[2:] #去掉前缀'0b'\n",
    "                break\n",
    "        #无需前面补零\n",
    "        if len(s1)==len(nums[0]):\n",
    "            return s1\n",
    "        #前面补零\n",
    "        else:\n",
    "            s2=(len(nums[0])-len(s1))*'0'\n",
    "            return s2+s1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\r\n",
    "        # return self.solveByCounter(nums)\r\n",
    "        return self.solveByDiagonal(nums)\r\n",
    "\r\n",
    "    def solveByCounter(self, nums: List[str]) -> str:\r\n",
    "        n = len(nums)\r\n",
    "        upper = 1 << n - 1\r\n",
    "        cnt = Counter([int(num, 2) for num in nums])\r\n",
    "        for i in range(upper + 1):\r\n",
    "            if cnt[i] == 0:\r\n",
    "                return bin(i)[2:].zfill(n)\r\n",
    "    \"\"\"\r\n",
    "        nums 的長度 n 和 字串的長度也是 n，\r\n",
    "        因此可以確保答案和每個數字都有一位不同\r\n",
    "    \"\"\"\r\n",
    "    def solveByDiagonal(self, nums: List[str]) -> str:\r\n",
    "        n = len(nums)\r\n",
    "        ans = \"\"\r\n",
    "        for i in range(n):\r\n",
    "            ans += \"1\" if nums[i][i] == \"0\" else \"0\"\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         n, st = len(nums), set()\n",
    "#         for v in nums: st.add(v)\n",
    "#         for i in range(1 << n, 1 << (n+1)):\n",
    "#             s = bin(i)[3:]\n",
    "#             if s not in st: return s\n",
    "#         return \"\"  # never!\n",
    "\n",
    "# class Solution(object):\n",
    "#     def findDifferentBinaryString(self, nums):\n",
    "#         res = ''\n",
    "#         for i in range(len(nums)):\n",
    "#             res += '1' if nums[i][i] == '0' else '0'\n",
    "#         return res\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        nums = set(nums)\n",
    "        return next(\n",
    "            s for p in product(\"01\", repeat=len(nums)) if (s := \"\".join(p)) not in nums\n",
    "        )\n",
    "\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         n = len(nums)\n",
    "#         # 预处理对应整数的哈希集合\n",
    "#         vals = {int(num, 2) for num in nums}\n",
    "#         # 寻找第一个不在哈希集合中的整数\n",
    "#         val = 0\n",
    "#         while val in vals:\n",
    "#             val += 1\n",
    "#         # 将整数转化为二进制字符串返回\n",
    "#         res = \"{:b}\".format(val)\n",
    "#         return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# # 借助python-bin函数 - O(n), O(n)\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         n, st = len(nums), set(nums)\n",
    "#         for i in range(1 << n, 1 << (n+1)):\n",
    "#             s = bin(i)[3:]\n",
    "#             if s not in st: return s\n",
    "#         return \"\"  # never!\n",
    "\n",
    "# # 网友题解1：O(n), O(1)\n",
    "class Solution(object):\n",
    "    def findDifferentBinaryString(self, nums):\n",
    "        res = ''\n",
    "        for i in range(len(nums)):\n",
    "            res += '1' if nums[i][i] == '0' else '0'\n",
    "        return res\n",
    "\n",
    "# # 网友题解2 - O(n), O(n)\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         nums = set(nums)\n",
    "#         return next(\n",
    "#             s for p in product(\"01\", repeat=len(nums)) if (s := \"\".join(p)) not in nums\n",
    "#         )\n",
    "\n",
    "# # 官方题解一：转化为整数 - O(n^2), O(n)\n",
    "# class Solution:\n",
    "#     def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "#         n = len(nums)\n",
    "#         # 预处理对应整数的哈希集合\n",
    "#         vals = {int(num, 2) for num in nums}\n",
    "#         # 寻找第一个不在哈希集合中的整数\n",
    "#         val = 0\n",
    "#         while val in vals:\n",
    "#             val += 1\n",
    "#         # 将整数转化为二进制字符串返回\n",
    "#         res = \"{:b}\".format(val)\n",
    "#         return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        hash_map = dict()\n",
    "        for num in nums:\n",
    "            hash_map[int(num, 2)] = 1\n",
    "        for i in range(0, 2 ** len(nums[0])):\n",
    "            if i not in hash_map.keys():\n",
    "                return self.ten2binary(i, len(nums[0]))\n",
    "\n",
    "    @staticmethod\n",
    "    def ten2binary(num, n):\n",
    "        result = []\n",
    "        while num:\n",
    "            result.append(str(num % 2))\n",
    "            num //= 2\n",
    "        return \"\".join([\"0\" * (n - len(result[::-1]))] + result[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return \"\".join(\"1\" if nums[i][i] == \"0\" else \"0\" for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        l = len(nums)\n",
    "        nums = set(nums)\n",
    "        top = 2**l\n",
    "        for n in range(top):\n",
    "            bit = bin(n)[2:].zfill(l)\n",
    "            if bit not in nums:\n",
    "                return bit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if i != int(nums[i], 2):\n",
    "                return bin(i)[2:].zfill(n)\n",
    "        return bin(n)[2:].zfill(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        nums = [int(x, 2) for x in nums]\n",
    "        us = set(nums)\n",
    "        \n",
    "        res = \"\"\n",
    "        x = 0\n",
    "        while x in us:\n",
    "            x += 1\n",
    "        res = bin(x)[2:]\n",
    "        return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        bits = len(nums[0])\n",
    "        binaries = [int(num, 2) for num in nums]\n",
    "        for search_binary in range(2 ** bits):\n",
    "            isMissing = True\n",
    "            for binary in binaries:\n",
    "                if search_binary ^ binary == 0:\n",
    "                    isMissing = False\n",
    "                    break\n",
    "            if isMissing:\n",
    "                return format(search_binary, f\"0{bits}b\")\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        retVal = \"\"\n",
    "\n",
    "        intNums = []\n",
    "        for num in nums:\n",
    "            intNum = int(num, 2)\n",
    "            intNums.append(intNum)\n",
    "\n",
    "        numsSize = len(nums)\n",
    "        maxRange = 1 << numsSize\n",
    "        for i in range(maxRange):\n",
    "            if i in intNums:\n",
    "                continue\n",
    "\n",
    "            retVal = str((bin(i)[2:]))\n",
    "            retVal = \"0\" * (numsSize - len(retVal)) + retVal\n",
    "            break\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        # 预处理对应整数的哈希集合\n",
    "        vals = {int(num, 2) for num in nums}\n",
    "        # 寻找第一个不在哈希集合中的整数\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "        # 将整数转化为二进制字符串返回\n",
    "        res = \"{:b}\".format(val)\n",
    "        return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            if nums[i][i] == \"0\":\n",
    "                ans += \"1\"\n",
    "            else:\n",
    "                ans += \"0\"\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        # 预处理对应整数的哈希集合\n",
    "        vals = {int(num, 2) for num in nums}\n",
    "        # 寻找第一个不在哈希集合中的整数\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "        # 将整数转化为二进制字符串返回\n",
    "        res = \"{:b}\".format(val)\n",
    "        return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        seen = set([int('0b' + ss, 2)for ss in nums])\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        for i in range(n + 1):\n",
    "            if i not in seen:\n",
    "                return bin(i)[2:].zfill(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        L = len(nums[0])\n",
    "        for i in range(len(nums)):\n",
    "            nums[i] = int(nums[i],2)\n",
    "        nums = set(nums)\n",
    "        for i in range(2**L):\n",
    "            if i not in nums:\n",
    "                res = bin(i)[2:]\n",
    "                for _ in range(L-len(res)):\n",
    "                    res = \"0\"+res\n",
    "                return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        st = set(int(x, 2) for x in nums)\n",
    "        # print(f'{st}')\n",
    "        n = len(nums[0])\n",
    "        for i in range(1 << n):\n",
    "            if i not in st:\n",
    "                # print(f'{i}')\n",
    "                ans = ''\n",
    "                for j in range(n - 1, -1, -1):\n",
    "                    ans += str(i >> j & 1)\n",
    "                return ans\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from random import randint\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: list[str]) -> str:\n",
    "        l = len(nums)\n",
    "        s = \"\"\n",
    "        for i in range(l):\n",
    "            s += str(randint(0, 1))\n",
    "        while s in nums:\n",
    "            s = \"\"\n",
    "            for i in range(l):\n",
    "                s += str(randint(0, 1))\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        ret = '1' * len(nums[0])\n",
    "        dq = deque(nums)\n",
    "        nums = set(nums)\n",
    "        while ret in nums:\n",
    "            tmp = list(int(x) for x in ret)\n",
    "            x = dq.popleft()\n",
    "            for i in range(len(x)):\n",
    "                tmp[i] ^= int(x[i])\n",
    "                ret = ''.join(map(str, tmp))\n",
    "                if ret not in nums:\n",
    "                    break\n",
    "            dq.append(x)\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        vals = set(int(x, 2) for x in nums)\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "        ret = str(bin(val))[2:]\n",
    "        return '0' * (len(nums) - len(ret)) + ret\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return ''.join(chr(ord(nums[i][i]) ^ 1) for i in range(len(nums)))\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return ''.join(str(int(nums[i][i]) ^ 1) for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: list[str]) -> str:\n",
    "        return ''.join(str((int(nums[i][i])^1)%2) for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums[0])\n",
    "        s = {int(num, 2) for num in nums}\n",
    "        for i in range(1 << n):\n",
    "            if i not in s:\n",
    "                return f'{i:0{n}b}'\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        _map = {\"1\": \"0\", \"0\": \"1\"}\n",
    "        return \"\".join([_map[nums[i][i]] for i in range(len(nums))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n=len(nums)\n",
    "        vals={int(val,2) for val in nums}\n",
    "        val=0\n",
    "        while val in vals:\n",
    "            val+=1\n",
    "        res=\"{:b}\".format(val)\n",
    "        return '0'*(n-len(res))+res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums[0])\n",
    "        ans = \"\"\n",
    "        for i in range(n):\n",
    "            j = nums[i][i]\n",
    "            if j == \"1\":\n",
    "                ans += \"0\"\n",
    "            else:\n",
    "                ans += \"1\"\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\r\n",
    "        # return self.solveByCounter(nums)\r\n",
    "        return self.solveByDiagonal(nums)\r\n",
    "\r\n",
    "    def solveByCounter(self, nums: List[str]) -> str:\r\n",
    "        n = len(nums)\r\n",
    "        upper = 1 << n - 1\r\n",
    "        cnt = Counter([int(num, 2) for num in nums])\r\n",
    "        for i in range(upper + 1):\r\n",
    "            if cnt[i] == 0:\r\n",
    "                return bin(i)[2:].zfill(n)\r\n",
    "    def solveByDiagonal(self, nums: List[str]) -> str:\r\n",
    "        n = len(nums)\r\n",
    "        ans = \"\"\r\n",
    "        for i in range(n):\r\n",
    "            ans += \"1\" if nums[i][i] == \"0\" else \"0\"\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return ''.join(chr(ord(nums[i][i])^1) for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\r\n",
    "        n = len(nums)\r\n",
    "        upper = 1 << n - 1\r\n",
    "        cnt = Counter([int(num, 2) for num in nums])\r\n",
    "        for i in range(upper + 1):\r\n",
    "            if cnt[i] == 0:\r\n",
    "                return bin(i)[2:].zfill(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        numSet = set()\n",
    "        for num in nums:\n",
    "            numSet.add(int(num, 2))\n",
    "        \n",
    "        n = len(num)\n",
    "        for i in range(2**n):\n",
    "            if i not in numSet:\n",
    "                res = bin(i)[2:]\n",
    "                return '0' * (n-len(res)) + res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        # 方法1、二进制\n",
    "        n = len(nums)\n",
    "        for mask in range(1 << n):\n",
    "            arr = []\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i):\n",
    "                    arr.append('1')\n",
    "                else:\n",
    "                    arr.append('0')\n",
    "            s = \"\".join(arr)\n",
    "            if s not in nums:\n",
    "                return s\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = set()\n",
    "        for num in nums:\n",
    "            n.add(int(num,2))\n",
    "        for i in range(2**len(nums)):\n",
    "            if i not in n:\n",
    "              final = str(bin(i)[2:])\n",
    "              return \"0\" * (len(nums) - len(final)) + final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        arr = [int(x, 2) for x in nums]\n",
    "        n = len(nums[0])\n",
    "        arr.sort()\n",
    "        if arr[0] > 0:\n",
    "            return \"0\" * n\n",
    "        if arr[-1] < int(\"1\"*n, 2):\n",
    "            return \"1\" * n\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i-1] > 1:\n",
    "                res = bin(arr[i]-1)[2:]\n",
    "                return \"0\" * (n-len(res)) + res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return ''.join('1' if nums[i][i] == '0' else '0' for i in range(len(nums)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums[0])\n",
    "        s = {int(num, 2) for num in nums}\n",
    "        for i in range(1 << n):\n",
    "            if i not in s:\n",
    "                return format(i, f'0{n}b')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        result, s = 0, {int(x, 2) for x in nums}\n",
    "        while result in s:\n",
    "            result += 1\n",
    "        return bin(result)[2:].zfill(len(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        if not nums:\n",
    "            return None\n",
    "        \n",
    "        nums.sort()\n",
    "        num = [0] * len(nums[0])\n",
    "        num[-1] = -1\n",
    "        for i in range(len(nums)):\n",
    "            num_str = self.increase(num)\n",
    "            if num_str != nums[i]:\n",
    "                return num_str\n",
    "        \n",
    "        return self.increase(num)\n",
    "\n",
    "\n",
    "    def increase(self, num):\n",
    "        num[-1] += 1\n",
    "        j = len(num) - 1\n",
    "        while num[j] >= 2:\n",
    "            num[j] -= 2\n",
    "            num[j - 1] += 1\n",
    "            j -= 1\n",
    "        \n",
    "        num_str = \"\".join([str(v) for v in num])\n",
    "        return num_str\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\r\n",
    "        n = [int(num, 2) for num in nums]\r\n",
    "        ans = 0\r\n",
    "        while ans in n:\r\n",
    "            ans += 1\r\n",
    "        return bin(ans)[2:].zfill(len(nums[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        # 预处理对应整数的哈希集合\n",
    "        vals = {int(num, 2) for num in nums}\n",
    "        # 寻找第一个不在哈希集合中的整数\n",
    "        val = 0\n",
    "        while val in vals:\n",
    "            val += 1\n",
    "            \n",
    "        # 将整数转化为二进制字符串返回\n",
    "        res = \"{:b}\".format(val)\n",
    "        return '0' * (n - len(res)) + res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        return \"\".join(\"1\" if nums[i][i] == \"0\" else \"0\" for i in range(len(nums)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        for i in range(1 << n):\n",
    "            tmp = bin(i)[2:].zfill(n)\n",
    "            if tmp not in nums:\n",
    "                return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        nums = [int(x, 2) for x in nums]\n",
    "        us = set(nums)\n",
    "        \n",
    "        res = \"\"\n",
    "        x = 0\n",
    "        while x in us:\n",
    "            x += 1\n",
    "        res = bin(x)[2:]\n",
    "        return '0' * (n - len(res)) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        def backtracking(s):\n",
    "            if len(s) == n:\n",
    "                if s in nums: return False\n",
    "                return s\n",
    "            return backtracking(s + \"0\") or backtracking(s + \"1\")\n",
    "\n",
    "        n = len(nums)\n",
    "        nums = set(nums)\n",
    "        return backtracking(\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:#题解的康托尔对角线方法\n",
    "        res=\"\"\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i][i]=='0':\n",
    "                res+='1'\n",
    "            else:res+='0'\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums[0])\n",
    "        nums = set(nums)\n",
    "        for i in range(1 << n):\n",
    "            s = bin(i)[2:].zfill(n)\n",
    "            if s not in nums:\n",
    "                return s\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        _map = {\"1\": \"0\", \"0\": \"1\"}\n",
    "        return \"\".join([_map[nums[i][i]] for i in range(len(nums))])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        def dfs(path) -> bool:\n",
    "            nonlocal res\n",
    "            if len(path) == n:\n",
    "                if path not in nums:\n",
    "                    res = path\n",
    "                    return True\n",
    "                return False\n",
    "            if dfs(path + '0'):\n",
    "                return True\n",
    "            if dfs(path + '1'):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        nums = set(nums)\n",
    "        n = len(nums)\n",
    "        res = None\n",
    "        dfs('')\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        # st = set(int(x) for x in nums)\n",
    "        st = set(nums)\n",
    "        # print(f'{st}')\n",
    "        n = len(nums[0])\n",
    "        for i in range(1 << n):\n",
    "            # print(f'{i}')\n",
    "            ans = ''\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                ans += str(i >> j & 1)\n",
    "            if ans not in st:\n",
    "                return ans\n",
    "        return \"\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        trie = {}\n",
    "        for num in nums:\n",
    "            node = trie\n",
    "            for x in num:\n",
    "                node = node.setdefault(x, {})\n",
    "            node['#'] = num\n",
    "        \n",
    "        def dfs(node, cnt):\n",
    "            if cnt == n:\n",
    "                return \"\"\n",
    "            if '0' not in node:\n",
    "                return \"0\"\n",
    "            if '1' not in node:\n",
    "                return \"1\"\n",
    "\n",
    "\n",
    "            ans = \"\"\n",
    "            for x in '01':\n",
    "                ans = x + dfs(node[x], cnt+1)\n",
    "            return ans\n",
    "        \n",
    "        ans = dfs(trie, 0)\n",
    "        return ans + '1' * (n - len(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        def backtracking(s):\n",
    "            if len(s) == n:\n",
    "                if s in nums: return False\n",
    "                return s\n",
    "            return backtracking(s + \"0\") or backtracking(s + \"1\")\n",
    "\n",
    "        n = len(nums)\n",
    "        nums = set(nums)\n",
    "        return backtracking(\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        se = set(nums)\n",
    "        def back(s):\n",
    "            if len(s) == n:\n",
    "                if s in se:\n",
    "                    return False\n",
    "                return s\n",
    "            return back(s + '0') or back(s + '1')\n",
    "        return back('')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums[0])\n",
    "        m = 1 << n \n",
    "        has = [False] * m\n",
    "        for s in nums:\n",
    "            w = m >> 1\n",
    "            ind = 0\n",
    "            for c in s:\n",
    "                ind |= w if (ord(c) - ord('0')) else 0\n",
    "                w >>= 1\n",
    "            has[ind] = True\n",
    "        ans = []\n",
    "        for i in range(m):\n",
    "            if not has[i]:\n",
    "                num = i\n",
    "                for k in range(0, n):\n",
    "                    ans.append(str(num & 1))\n",
    "                    num >>= 1\n",
    "                break\n",
    "        ans.reverse()\n",
    "        return \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "        n = len(nums)\n",
    "        vst = [0] * (1 << n)\n",
    "        for s in nums:\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if s[i] == '1':\n",
    "                    cnt |= 1 << (n - i - 1)\n",
    "            vst[cnt] = 1\n",
    "        # print(vst)\n",
    "        i = 0\n",
    "        while vst[i]:\n",
    "            i += 1\n",
    "        ret = bin(i)[2:]\n",
    "        return '0' * (n - len(ret)) + ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findDifferentBinaryString(self, nums: List[str]) -> str:\n",
    "\n",
    "        n = len(nums[0])\n",
    "        res = 2 ** n\n",
    "        final = 0\n",
    "        ans = []\n",
    "        res_1 = []\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            ans.append(int(nums[i],2))\n",
    "        for i in range(res):\n",
    "            res_1.append(i)\n",
    "        for i in res_1:\n",
    "            if i not in ans:\n",
    "                final = bin(i)\n",
    "\n",
    "        final = str(final)[2:]\n",
    "        if len(final) < n:\n",
    "            final = \"0\" * (n - len(final)) + final\n",
    "\n",
    "        return final\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
